#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dato.h"
#include "arbol.h"

void crear_arbol(t_arbol *pa)
{
    *pa = NULL;
}

int altura(t_arbol *pa){
    int hi,hd;
    if(*pa){
        hi=altura(&(*pa)->izq);
        hd=altura(&(*pa)->der);
        return hi>hd? hi+1:hd+1;
    }
    return 0;
}

void trabajar_etiqueta(t_etiqueta *et){
    printf("numero: %ld \n" ,et->dni );
}

void recorrer_en_orden(t_arbol *pa,void(*func)(t_etiqueta*)){
    if(*pa){
        recorrer_en_orden(&(*pa)->izq,func);
        func(&(*pa)->et);
        recorrer_en_orden(&(*pa)->der,func);
    }
}

int comparar(t_etiqueta *e1, t_etiqueta *e2){
    if(e1->dni==e2->dni)
        return 0;
    if(e1->dni>e2->dni)
        return -1;
    else
        return 1;
}

int insertar_en_arbol(t_arbol *pa,const t_etiqueta *pe, t_cmp comparar){
    t_nodo_doble *pn;
    int resp;
    if(!*pa){
        pn=(t_nodo_doble*)malloc(sizeof(t_nodo_doble));
        if(!pn){
            return 0;
        }
        pn->der=pn->izq=NULL;
        pn->et=*pe;
        *pa=pn;
        return 1;
    }else{
        resp = comparar(&(*pa)->et, pe);
        if(resp==0)
            return 0;
        if (resp>0)
            return insertar_en_arbol(&(*pa)->der,pe, comparar);
        return insertar_en_arbol(&(*pa)->izq,pe, comparar);

    }
}
t_arbol * mayor(const t_arbol *pa){
    if(!*pa)
        return NULL;
    if((*pa)->der==NULL){
        return pa;
    }else{
        return mayor(&(*pa)->der);
    }
}
t_arbol * menor(const t_arbol *pa){
    if(!*pa)
        return NULL;
    if((*pa)->izq==NULL){
        return pa;
    }else{
        return menor(&(*pa)->izq);
    }
}

void eliminar_raiz(t_arbol *pa){
    int hi, hd;
    t_arbol *paux;
    if(!*pa)
        return;
    if((!(*pa)->izq)&&(!(*pa)->der)){
        free(*pa);
        *pa=NULL;
        return;
    }
    hi = altura(&(*pa)->izq);
    hd = altura(&(*pa)->der);
    paux = hi>hd?mayor(&(*pa)->izq):menor(&(*pa)->der);
    (*pa)->et = (*paux)->et;
    eliminar_raiz(paux);
    return;
}

t_arbol* buscar_etiqueta(const t_arbol *pa,const t_etiqueta *pe, t_cmp cmp){
    int comp;
    if(!*pa)
        return NULL;
    comp=cmp(&(*pa)->et,pe);
    if(!comp)
        return pa;
    if(comp<0)
        return buscar_etiqueta(&(*pa)->izq,pe,cmp);
    return buscar_etiqueta(&(*pa)->der,pe,cmp);
}

int eliminar_etiqueta( t_arbol *pa, const t_etiqueta *pe, t_cmp cmp){
    t_arbol * paux;
    paux=buscar_etiqueta(pa, pe,cmp);
    if (paux){
        eliminar_raiz(paux);
        return 1;
    }else{
        return 0;
    }
}
int arbol_balanceado(t_arbol *pa)
{
    if(*pa)
        return altura(&(*pa)->izq) == altura(&(*pa)->der) ? 1 : 0;
    return 1;
}
int arbol_avl(t_arbol *pa)
{
    int hi = altura(&(*pa)->izq), hd = altura(&(*pa)->der);
    if(hi == hd +1 || hi+1 == hd || hd == hi)
        return 1;
    return 0;
}

void vaciar_arbol(t_arbol *pa)
{
    if(*pa)
    {
        vaciar_arbol(&(*pa)->izq);
        vaciar_arbol(&(*pa)->der);
        free(*pa);
        *pa = NULL;
    }
}

int arbol_vacio(const t_arbol *pa)
{
    if(!(*pa))
        return 1;
    return 0;
}

int arbol_lleno(const t_arbol *pa)
{
    t_nodo_doble *pn = (t_nodo_doble*)malloc(sizeof(t_nodo_doble));
    if(!pn)
        return 1;
    return 0;
}
